'''
Created on 2024年8月13日

@author: Administrator
'''

def get_next(pat):
    m = len(pat)
    n = [-1]*m
    
    i = 0
    j = -1
    while i<m-1:
        if j == -1 or pat[i] == pat[j]:
            i+=1
            j+=1
            if pat[i] == pat[j]:
                n[i] = n[j]
            else:
                n[i] = j
        else:
            j = n[j]
            
    
    return n
def kmp_search(pat,s):
    
    n = get_next(pat)
    
    m = len(pat)
    ns = len(s)
    
    i = 0
    j = 0
    while i<ns and j<m:
        if j == -1 or s[i] == pat[j]:
            i += 1
            j += 1
        else:
            j = n[j]
            
    
    if j == m:
        return i-j
    else:
        return -1
      
if __name__ == '__main__':
    print(get_next("abcabc_abc"))  
    print(get_next("aaaaaab"))
    pat = "aaaab"
    s = "sssssaaadddaaaabaaaabeeeee"
    
    print(kmp_search(pat, s))
    print(kmp_search("", s))
    print(s[kmp_search("", s)])  
           
    
    



